package com.leetcode.code;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Description:
 * 给定一个没有重复数字的序列，返回其所有可能的全排列。
 *
 * 示例:
 *
 * 输入: [1,2,3]
 * 输出:
 * [
 * [1,2,3],
 * [1,3,2],
 * [2,1,3],
 * [2,3,1],
 * [3,1,2],
 * [3,2,1]
 * ]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/permutations
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author zkingcobra
 * Date: 2019/10/25 9:31 上午
 */
public class LeetCode0046Java {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.permute(new int[] { 1, 2, 3 }));
    }

    static class Solution {
        int first = 0;
        int index = 0;

        List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> output = new ArrayList<List<Integer>>();

            ArrayList<Integer> nums_lst = new ArrayList<Integer>();

            for (int num : nums) {
                nums_lst.add(num);
            }

            int n = nums.length;

            backtrack(n, nums_lst, output, 0);

            return output;
        }

        private void backtrack(int n, ArrayList<Integer> nums, List<List<Integer>> output, int first) {

            if (first == n) {
                output.add(new ArrayList<Integer>(nums));
            }

            for (int i = first; i < n; i++) {
                // place i-th integer first
                // in the current permutation
                Collections.swap(nums, first, i);
                // use next integers to complete the permutations
                backtrack(n, nums, output, first + 1);
                // backtrack
                Collections.swap(nums, first, i);
            }
        }
    }
}
